from typing import Optional
from python.mypackage import TreeNode


class Solution:

    """
    方法：flatten 将二叉树展开为链表
    
    使用后序遍历的方式（右-左-根）将二叉树展开为链表。
    通过维护一个全局的head指针，将当前节点的右指针指向之前处理的节点，
    并将左指针置为空，从而实现二叉树到链表的转换。
    
    Args:
        root: Optional[TreeNode] - 二叉树的根节点
    
    Returns:
        None - 直接在原树上修改
    
    Time: O(n) - 其中n是二叉树的节点数，每个节点只被访问一次
    
    Space: O(h) - 其中h是二叉树的高度，递归调用栈的空间
    """
    head = None
    def flatten(self, root: Optional[TreeNode]) -> None:
        if root is None:
            return
        self.flatten(root.right)
        self.flatten(root.left)
        root.left = None
        root.right = self.head
        self.head = root

    """
    方法：flatten1 将二叉树展开为链表（迭代方式）
    
    通过迭代方式将二叉树展开为链表。对于每个节点，如果它有左子树，
    则找到左子树的最右节点，将当前节点的右子树接到这个最右节点的右指针上，
    然后将左子树移到右子树的位置，并将左指针置为空。
    
    Args:
        root: Optional[TreeNode] - 二叉树的根节点
    
    Returns:
        None - 直接在原树上修改
    
    Time: O(n) - 其中n是二叉树的节点数，每个节点最多被访问两次
    
    Space: O(1) - 只使用常数额外空间
    """

    def flatten(self, root: Optional[TreeNode]) -> None:
        cur = root
        while cur:
            if cur.left:
                pre = next = cur.left
                while pre.right:
                    pre = pre.right
                pre.right = cur.right
                cur.left = None
                cur.right = next
            cur = cur.right